package main

import "fmt"

func main() {
	s := "ADOBECODEBANC"
	t := "ABC"
	fmt.Println(minWindow(s, t))
}

/**
 * @Description:给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * @t:套用滑动窗口模板
 */
func minWindow(s string, t string) string {
	need, window := make(map[byte]int), make(map[byte]int)
	validLen := 0
	start, maxLen := 0, 1<<32
	left, right := 0, 0
	//初始化需要的信息
	for _, letter := range []byte(t) {
		need[letter]++
	}

	for right < len(s) {
		sLetter := s[right]
		//窗口向右滑动
		right++
		if value, ok := need[sLetter]; ok {
			window[sLetter]++
			//当窗口里的数量与需要的数量相等，则有效值+1
			if window[sLetter] == value {
				validLen++
			}
		}
		//当有效长度等于需要的长度时，判断是否要缩小窗口
		for validLen == len(need) {
			//在这里更新最小覆盖子串
			if right-left < maxLen {
				start = left
				maxLen = right - left
			}
			tLetter := s[left]
			left++
			if value, ok := need[tLetter]; ok {
				//当窗口里的数量与需要的数量相等，则有效值-1
				if window[tLetter] == value {
					validLen--
				}
				window[tLetter]--
			}
		}
	}
	if maxLen == 1<<32 {
		return ""
	} else {
		return s[start : start+maxLen]
	}
}
